package seqlist;

/**
 * 带头（虚拟头节点）单链表
 */
public class LinkedListWithHead {
    private int size;//当链表中有效数据的个数（不包含头节点）
    //实实在在存在的Node对象，不存储数据，就作为火车头
    private Node dummyHead = new Node();

    public void addFirst(int val){
        Node node=new Node();
        node.val=val;
        node.next=dummyHead.next;
        dummyHead.next=node;
        size++;
//        2.
//        Node node = new Node();
//        dummyHead.next=node;
        //3.dummyHead.next = new Node(val.dummyHead.next);
    }

    public void add(int index,int val){
        if(index<0||index>size){
            System.err.println("add index illagal!");
            return;
        }
        Node prev =dummyHead;
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        Node node=new Node();
        node.val=val;
        node.next=prev.next;
        prev.next=node;
//        2.Node node = new Node(val.prev.next);
//          prev.next=node;
//        3.dummyHead.next = new Node(prev.next);
        size++;

    }

    /**
     * 删除单链表中索引为index位置的节点，返回删除前的节点值
     * @param index
     * @return
     */
    public int remove(int index){
            if (rangeCheck(index)){
                Node prev= dummyHead;
                for (int i = 0; i < index; i++) {
                    prev=prev.next;
                }
                Node cur=prev.next;
                prev.next=cur.next;
                int val= cur.val;
                cur.next=cur=null;
                size--;
                return val;
            }
        System.out.println("index illegal");
            return -1;
    }
    public void removeAllvalue(int val){
        Node prev=dummyHead;
        while (prev.next!=null){
            if (prev.next.val==val){
                prev.next=prev.next.next;
                size--;
            }else {
                prev=prev.next;
            }
        }
    }

    public String toString(){
        String ret="";
        for (Node x=dummyHead.next;x!=null;x=x.next){
            ret+=x.val;
            ret+="->";
        }
        ret+="null";
        return ret;
    }
    private boolean rangeCheck(int index) {
        if (index<0||index>=size){
            return false;
        }
        return true;
    }

}
